 class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

 /**
  * 543. 二叉树的直径
  * https://leetcode.cn/problems/diameter-of-binary-tree/description/?envType=study-plan-v2&envId=top-100-liked
  */
 class Solution {
    int ret;
    public int diameterOfBinaryTree(TreeNode root) {
        ret = 1;
        depth(root);
        return ret - 1;
    }
    public int depth(TreeNode node) {
        if(node == null) {
            return 0;
        }
        int L = depth(node.left);
        int R = depth(node.right);
        ret = Math.max(ret, L+R+1);
        return Math.max(L, R) + 1;
    }
}